紅黑樹（Red–Black Tree）

Deletion

Case 1: x 的兄弟 w 為紅色

Case 2: x 的兄弟 w 為黑色，且 w 的兩個子節點皆為黑

Case 3: x 的兄弟 w 為黑色，w 的左節點為紅，右節點為黑

Case 4: x 的兄弟 w 為黑色，且 w 的兩個子節點皆為紅

RB-DELETE-FIXUP(T, x)
    while x != T.root and x.color == BLACK
        if x == x.p.left
            w = w.p.right
            
            // Case 1
            if w.color == RED
                w.color = BLACK
                x.p.color = RED
                LEFT-ROTATE(T.x, p)
                w = x.p.right
            
            // Case 2
            if w.left.color == BLACK and w.right.color == BLACK
                w.color = RED
                x = x.p
            
            // Case 3
            else if w.right.color == BLACK
                w.left.color = BLACK
                w.color = RED
                RIGHT-ROTATE(T, w)
                w = x.p.right
            
            //Case 4
            w.color = x.p.color
            x.p.color = BLACK
            w.right.color = BLACK
            LEFT-ROTATE(T, x.p)
            x = T.root
        else (same as then clause with "right" and "left" exchanged)
    x.color = BLACK